﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/search-insert-position
/*
题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，
返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

*/

// 方法1——直接遍历法
/*
思路：
直接遍历数组，如果找到targe就返回其下标
当出现nums[i] < target && nums[i + 1] > target时，
nums[i + 1]就是target要顺序加入的下标
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int searchInsert1(int* nums, int numsSize, int target) {
	// 特殊情况特殊处理
	if (target < nums[0]) {
		return 0;
	}
	else if (target > nums[numsSize - 1]) {
		return numsSize;
	}
	int i = 0;
	for (i = 0; i < numsSize; i++) {
		if (nums[i] == target) {
			return i;
		}
		else if (nums[i] < target && nums[i + 1] > target) {
			return i + 1;
		}
	}
	return numsSize;
}

// 方法2——二分查找
/*
思路：
在一个有序数组中查找目标值，很容易的就能想到用二分查找法
如果通过mid找到了目标值，则直接返回mid，如果找不到就返回left
因为left右移的条件一定是target > mid, 所以这就等同于向后寻找更大的数
当最后停下来时，一定是left > right 且 left 等于上一轮的mid + 1，
也就是说mid >target > left
所以left就是target最后要按顺序插入的位置
*/

//有了以上思路，那我们写起代码来也就水到渠成了
int searchInsert(int* nums, int numsSize, int target) {
	assert(nums);
	// 特殊情况特殊处理
	if (target < nums[0]) {
		return 0;
	}
	int left = 0;
	int right = numsSize - 1;
	int mid = 0;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (target == nums[mid]) {
			return mid;
		}
		else if (target > nums[mid]) {
			left = mid + 1;
		}
		else if (target < nums[mid]) {
			right = mid - 1;
		}
	}
	return left;
}

int main() {
	int nums[] = { 1, 3, 5, 6 };
	int nums_size = sizeof(nums) / sizeof(nums[0]);
	int result = searchInsert(nums, nums_size, 2);
	printf("%d", result);
	return 0;
}